from itertools import accumulate
from typing import List


class Solution:
    def canThreePartsEqualSum(self, arr: List[int]) -> bool:

        prefix = [0] + list(accumulate(arr))
        n = len(arr)

        def bisect(target):
            left = 0
            right = n
            while left <= right:
                mid = (left + right) >> 1
                if prefix[mid] == target:
                    return mid
                if prefix[mid] > target:
                    right = mid - 1
                else:
                    left = mid + 1
            return -1

        for i in range(n):
            prev = prefix[i + 1]
            id1 = bisect(2 * prev)
            id2 = bisect(3 * prev)
            if id1 != -1 and id2 != -1:
                return True
        return False


if __name__ == '__main__':
    s = Solution()
    r = s.canThreePartsEqualSum(arr=[3, 3, 6, 5, -2, 2, 5, 1, -9, 4])
    print(r)
